import java.util.ArrayList;
import java.util.List;

/**
* @description: 797. 所有可能的路径
* @author hewei
* @date 2022/8/25 14:32
* @version 1.0
*/

public class AllPathsSourceTarget {

    List<List<Integer>> ans;
    List<Integer> list;
    int[][] graph;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        ans = new ArrayList<>();
        list = new ArrayList<>();
        list.add(0);
        this.graph = graph;
        dfs(0);
        return ans;
    }

    public void dfs(int i) {
        if (i == graph.length - 1) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int a : graph[i]) {
            list.add(a);
            dfs(a);
            list.remove(list.size() - 1);
        }
    }
}
